ArrayList源码分析

发表于 | 分类于 | 阅读次数:

继承关系

1
2
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是开发者广泛使用的java集合，它继承自AbstractList 实现了List接口，支持随机访问以及拷贝，持久化。

本篇主要对ArrayList的实现进行分析，首先我们看它的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ArrayList(int initialCapacity) {
        super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    this.elementData = new Object[initialCapacity];
}

public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
 }

 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

ArrayList的构造方法很简单，主要是初始化elementData值，它是一个Object数组用来存储我们的元素。根据参数的不同实现也不同。

元素添加

1
2
3
4
5
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

首先调用ensureCapacityInternal来确保有足够的容量来存储e,随后将e保存在elementData数组中并增加size值 默认返回true。

在指定索引处添加元素

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

这个方法将元素element添加到数组中指定的index位置，所以效率上比add要慢，因为可能需要对数组元素进行挪动。同样这里需要保证足够的空间，并在添加完成后增加size计数。

对于Add方法，这里需要注意的是当elemmentData数组为空时，如果执行add(1,E)时会抛出IndexOutOfBoundsException这是因为在Add之前通过rangeCheckForAdd检查了index的值是否在[0,size]的区间，如果不再该区间那么抛出该异常。

1
2
3
4
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

元素删除

元素的删除有两个版本，分别针对索引和元素进行删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

通过索引删除，需要先对index做检测，删除index必须小于size,否则会报IndexOutOfBoundsException，然后从数组中取出index对应的元素oldValue，作为结果返回，随后计算需要移动的元素个数，然后通过System.arracopy完成index后面元素的移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

通过元素删除首先判断要删除的元素o是否为null，如果为null，遍历当前数组找到对应的索引然后通过fastRemove删除，如果o不为null,则通过其equals方法在数组中找到对应的元素索引，然后通过fastRemove删除。

1
2
3
4
5
6
7
8
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

这里有个问题：可以用for循环直接删除ArrayList的特定元素？
答案是不可以，不同的for循环删除可能错误都不同，如果时一般的for循环则只能删除一个元素，而如果使用泛型for删除的话会抛出ConcurrentModificationException，使用泛型for会用到List内部的迭代器Itr，它在通过next遍历元素时会通过checkForComodification检查ArrayList的modCount和expectedModCount是否一直，不一致的话就会抛出ConcurrentModificationException异常。

1
2
3
4
5
6
7
8
ArrayList<String> arr = new ArrayList<String>();
arr.add()
...
for(String item:arr){
    if(item.equals(...)){
        arr.remove(item);
    }
}

这种删除方式在remove方法中删除元素会更新modCount计数，而expectedModCount只会在迭代器版本的remove方法中更新，所以导致了不一致的情况，正确的方法是使用list.iterator()对ArrayList循环删除。

扩容

我们看看ensureCapacityInternal是如何保证容量大小的，即ArrayList如何进行扩容的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

 private void grow(int minCapacity) {
        // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

DEFAULT_CAPACITY默认为10，也就是说第一次添加到ArrayList的时候会开辟大小为10的数组。如果需要的大小大于当先数组的大小需要调用grow来完成容量的增加。

grow的resize逻辑如下：

  1. 计算新的容量大小为 int newCapacity = oldCapacity + (oldCapacity >> 1)这个新的容量为原来的1.5倍。
  2. 如果新的容量小于我们需要的 则以我们需要的为准开辟空间
  3. 如果新的容量大于最大可以开辟的容量值(Integer.MAX_VALUE - 8)，那么需要hugeCapacity进行大容量的分配
  4. 使用Arrays的copyOf将原数组resize到指定大小
坚持原创技术分享，您的支持将鼓励我继续创作！